package interview.algorithms.list;

import common.ListNode;
import common.Util;
import org.junit.Test;

import java.util.HashMap;

/**
 * @author fance
 * @date 2018/5/15 14:53
 */
public class Solution {

    /**
     * 删除重复数据
     * 1. hashmap 2.双重遍历
     * @param head
     */
    public void delDupI(ListNode head) {
        if (head == null) {
            return;
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        ListNode tmp = head;
        ListNode pre = null;
        while (tmp != null) {
            if (map.containsKey(tmp.val)) {
                pre.next = tmp.next;
            } else {
                map.put(tmp.val,1);
                pre = tmp;
            }
            tmp = tmp.next;
        }
    }
    public void delDupII(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode tmp = head;
        while (tmp != null) {
            ListNode cur = tmp;
            while (cur.next != null) {
                if (tmp.val == cur.next.val) {
                    cur.next = cur.next.next;
                } else {
                    cur = cur.next;
                }
            }
            tmp = tmp.next;
        }
    }

    /**
     * 倒数第k个节点
     * p1 先走k - 1 步，然后p1,p2一起走
     * @param head
     * @param k
     * @return
     */
    public ListNode findLastKth(ListNode head, int k) {
        if (k < 1) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < k - 1; i++) {
            p1 = p1.next;
        }
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }

    /**
     * 反转链表
     * @param head
     */
    private ListNode reverseList(ListNode head) {
        ListNode reverseHead = head;
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null) {
            ListNode next = cur.next;
            if (next == null) {
                reverseHead = cur;
            }

            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return reverseHead;
    }

    /**
     * 从尾到头打印
     * @param head
     */
    public void printListReverse(ListNode head) {
        if (head != null) {
            printListReverse(head.next);
            System.out.println(head.val);
        }
    }

    /**
     * 是否有环
     * @param head
     * @return
     */
    public boolean hasLoop(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 环入口
     * @param head
     * @return
     */
    public ListNode findLoopPort(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    /**
     * 链表右移k位
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateK(ListNode head, int k) {
        if (head == null) {
            return head;
        }
        int len = Util.getListLen(head);
        k = k % len;
        if (k == 0) {
            return head;
        }
        ListNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        // 将链表成环
        tmp.next = head;
        tmp = head;
        int offset = len - k;
        ListNode newHead;
        for (int i = 0; i < offset - 1; i++) {
            tmp = tmp.next;
        }
        newHead = tmp.next;
        tmp.next = null;
        return newHead;
    }

    @Test
    public void test() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        Util.printList(listNode1);

        Util.printList(rotateK(listNode1,1));
    }

}
